<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Global constraints
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial057.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial053.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial059.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc119">8.5</A>&nbsp;&nbsp;Global constraints</H2><UL>
<LI><A HREF="tutorial058.html#toc63">Different strengths of propagation</A>
</UL>

<A NAME="secglobal"></A>
<A NAME="@default207"></A>
<A NAME="@default208"></A>
The IC constraint solver has some optional components which provide
so-called <EM>global</EM> constraints. These are high-level constraints that
tend to provide more global reasoning than the constraints in the main IC
library. These optional components are contained in the <TT>ic_global</TT>,
<TT>ic_cumulative</TT>,<A NAME="@default209"></A>
<TT>ic_edge_finder</TT><A NAME="@default210"></A>
and <TT>ic_edge_finder3</TT><A NAME="@default211"></A>
libraries. The <TT>ic_global</TT> library provides a collection of general
global constraints, while the others provide constraints for
resource-constrained scheduling.<BR>
<BR>
To use these global constraints, load the relevant optional library or
libraries using directives in one of these forms:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- lib(ic_global).
:- use_module(library(ic_global)).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
Specify this at the beginning of your program.<BR>
<BR>
Note that some of these libraries provide alternate implementations of
predicates which also appear in other libraries. For example, the
<TT>alldifferent/1</TT> constraint is provided by both the standard
<TT>ic</TT> library and the <TT>ic_global</TT> library. This means that if
you wish to use it, you must use the relevant module qualifier to specify
which one you want:
<A HREF="../bips/lib/ic/alldifferent-1.html"><B>ic:alldifferent/1</B></A><A NAME="@default212"></A> or
<A HREF="../bips/lib/ic_global/alldifferent-1.html"><B>ic_global:alldifferent/1</B></A><A NAME="@default213"></A>.
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>&#8857;</B><DD CLASS="dd-description"> <FONT COLOR="#9832CC">See the &#8220;Additional Finite Domain Constraints&#8221; section of the Library
Manual for more details of these libraries and a full list of the predicates
they provide.</FONT>
</DL>

<A NAME="toc63"></A>
<H3 CLASS="subsection"><A NAME="htoc120">8.5.1</A>&nbsp;&nbsp;Different strengths of propagation</H3>
The <TT>alldifferent(List)</TT> predicate imposes the constraint on the
elements of <TT>List</TT> that they all take different values.
The standard <A HREF="../bips/lib/ic/alldifferent-1.html"><B>alldifferent/1</B></A><A NAME="@default214"></A>
predicate from the IC library provides a level of propagation equivalent to
imposing pairwise
<A HREF="../bips/lib/ic/HRE-2.html"><B>#\=/2</B></A>
<A NAME="@default215"></A>constraints (though it does it more efficiently than that). This means that
no propagation is performed until elements of the list start being made
ground. This is despite the fact that there may be &#8220;obvious&#8221; inferences
which could be made.<BR>
<BR>
Consider as an example the case of 5 variables with domains <TT>1..4</TT>.
Clearly the 5 variables cannot all be given different values, since there
are only 4 distinct values available. However, the standard
<A HREF="../bips/lib/ic/alldifferent-1.html"><B>alldifferent/1</B></A><A NAME="@default216"></A> constraint
cannot determine this:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- L = [X1, X2, X3, X4, X5], L :: 1 .. 4, ic:alldifferent(L).
X1 = X1{1 .. 4}
X2 = X2{1 .. 4}
X3 = X3{1 .. 4}
X4 = X4{1 .. 4}
X5 = X5{1 .. 4}
L = [X1{1 .. 4}, X2{1 .. 4}, X3{1 .. 4}, X4{1 .. 4}, X5{1 .. 4}]
There are 5 delayed goals.
Yes
</PRE></BLOCKQUOTE>
Consider another example where three of the variables have domain
<TT>1..3</TT>. Clearly, if all the variables are to be different, then no
other variable can take a value in the range <TT>1..3</TT>, since each of
those values must be assigned to one of the original three variables.
Again, the standard 
<A HREF="../bips/lib/ic/alldifferent-1.html"><B>alldifferent/1</B></A><A NAME="@default217"></A> constraint 
cannot determine this:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- [X1, X2, X3] :: 1 .. 3, [X4, X5] :: 1 .. 5,
   ic:alldifferent([X1, X2, X3, X4, X5]).
X1 = X1{1 .. 3}
X2 = X2{1 .. 3}
X3 = X3{1 .. 3}
X4 = X4{1 .. 5}
X5 = X5{1 .. 5}
There are 5 delayed goals.
Yes
</PRE></BLOCKQUOTE>
On the other hand, <TT>ic_global</TT>'s
<A HREF="../bips/lib/ic_global/alldifferent-1.html"><B>alldifferent/1</B></A><A NAME="@default218"></A>
constraint performs some stronger, more global reasoning, and for both of
the above examples makes the appropriate inference:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
?- L = [X1, X2, X3, X4, X5], L :: 1 .. 4, ic_global:alldifferent(L).
No

?- [X1, X2, X3] :: 1 .. 3, [X4, X5] :: 1 .. 5,
   ic_global:alldifferent([X1, X2, X3, X4, X5]).
X1 = X1{1 .. 3}
X2 = X2{1 .. 3}
X3 = X3{1 .. 3}
X4 = X4{[4, 5]}
X5 = X5{[4, 5]}
There are 2 delayed goals.
Yes
</PRE></BLOCKQUOTE>
Of course, there is a trade-off here: the stronger version of the constraint
takes longer to perform its propagation. Which version is best depends on
the nature of the problem being solved.
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>&#8857;</B><DD CLASS="dd-description"> <FONT COLOR="#9832CC">Note that even stronger propagation can be achieved if desired, by
using the Propia library (see Chapter&nbsp;</FONT><A HREF="tutorial107.html#chappropiachr"><FONT COLOR="#9832CC">15</FONT></A><FONT COLOR="#9832CC">).</FONT>
</DL>

<A NAME="@default219"></A>
In a similar vein, the <TT>ic_cumulative</TT>, <TT>ic_edge_finder</TT> and
<TT>ic_edge_finder3</TT> libraries provide increasingly strong versions of
constraints such as <TT>cumulative/4</TT>, but with increasing cost to do
their propagation (linear, quadratic and cubic, respectively).<BR>
<BR>
<A NAME="@default220"></A><BR>
<BR>
<HR>
<A HREF="tutorial057.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial053.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial059.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
